Evaluation of community detection methods

See also Cluster validation for general clustering validation.

Internal and external evaluation are the primary ways to evaluate and compare methods. Internal evaluation uses a quality measure (e.g., Modualrity) to compare and evaluate different Community detection methods. External evaluation uses either synthetic or real data.

When using synthetic data (“benchmark” approach), we plant Community structure into a network based on a model of community structure and then ask whether a given method can recover the planted communities. This is of course much cleaner than working with real data. However, one should note that we are planting the communities based on a model of such structure and therefore it will not be fair to compare methods that are based on different models of community structure. For instance, if we plant partitions based on a Stochastic block model, we are assuming that each community is more or less a random graph, and thus does not exhibit local structure (e.g., clustering). Therefore, methods that rely on local clustering (e.g., Clique percolation or Link community) would not work, whereas Stochastic block model-based community detection would work best. Likewise, if we plant pervasively overlapping community structure that is cliquish, Clique percolation would work much better than Stochastic block model or Modularity optimization methods.

Furthermore, there is also the issue of comparing identified community structure to the planted partition (see Clustering comparison). The most common approach is using Normalized mutual information or adjusted Rand index. However, these measures have critical biases (see Gates2019element).

It is also common to use metadata of real-world networks to evaluate community detection methods. For instance Choobdar2019assessment performed a systematic evaluation of many methods based on their usefulness in biological tasks. Yet, as shown in Peel2017ground and Hric2014community, it is usually not a good idea to consider metadata as “ground truth” communities. Still, evaluation methods that use metadata such as Gene set enrichment analysis are most commonly used methods in application of community detection.

Given “ground truth” (or rather reference clustering), Mutual information is often used. An important, overlooked question is how good the ground truth is. Some work about tagged networks¹²³.

Overlapping community structure makes the problem harder. For instance, Mutual information should be extended to covers. There are two proposals⁴⁵. There are other suggestions: using conductance of boundary nodes⁶.

Measures

• Rand index
  • Omega index

Statistical significance of communities: http://www.pnas.org/content/108/18/7321.short ; http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0018961

An approach to use data⁷.

References

• http://www.cse.chalmers.se/~moradi/Lic/SEA.pdf (http://sea2012.labri.fr/index.php?n=Main.Papers)
• http://arxiv.org/abs/1006.0375 - Information theoretic model validation for clustering

How can we define statistical significance? What will be the proper null models for community structure?

• http://pre.aps.org/abstract/PRE/v81/i4/e046110 - Statistical significance of communities in networks
  • http://arxiv.org/abs/1012.2363 - Finding statistically significant communities in networks
• http://prl.aps.org/abstract/PRL/v105/i22/e220601 - Significance Analysis and Statistical Mechanics: An Application to Clustering
• http://arxiv.org/abs/1110.0305 - Significant communities in large sparse networks

There are approaches to use online social network services such as Facebook (http://fellows-exp.com/).

• Comparing network covers using mutual information
• Defining and Evaluating Network Communities based on Ground-truth

• Community detection: effective evaluation on large social networks

  • network community benchmark
  • http://sociograph.blogspot.com/2013/11/facebook-benchmark-utility-released-on.html

• A revisit to evaluating accuracy of community detection using the normalized mutual information